package io.adrainty.algorithm.leetcode.lcr;

/**
 * LCR 003. 比特位计数
 * @link <a href="https://leetcode.cn/problems/w3tCBm/description/">...</a>
 * @author AdRainty
 * @version V1.0.0
 * @since 2024/8/29 上午12:18
 */
public class LCR003 {

    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // 1. i & (i - 1) 将尾部1变为0
            // 2. 也就是说 整数i的二进制形式中的1的个数 比 i & (i - 1)的二进制形式中的1的个数多1
            res[i] = res[i & (i - 1)] + 1;
            // 1. i >> 1 相当于 i / 2
            // 2. i & 1 相当于 i % 2
            // 例如 6的 1 的个数，等于3的1的个数 7 的1的个数, 等于3的1的个数 + 1
            // res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }

}
